package com.hspedu.newData.dmsxl.图;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-28 
 * @Version: 1.0
 */

public class LC417太平洋大西洋水流问题 {

    private int[][] dir = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
    public List<List<Integer>> pacificAtlantic(int[][] heights) {

        int m = heights.length;
        int n = heights[0].length;

        boolean[][] b1 = new boolean[m][n];
        boolean[][] b2 = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            dfs(b1,heights,i,0,Integer.MIN_VALUE);
            dfs(b2,heights,i,n-1,Integer.MIN_VALUE);
        }

        for (int i = 0; i < n; i++) {
            dfs(b1,heights,0,i,Integer.MIN_VALUE);
            dfs(b2,heights,m-1,i,Integer.MIN_VALUE);
        }

        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (b1[i][j]&&b2[i][j]){
                    List<Integer> path = new ArrayList<>();
                    path.add(i);
                    path.add(j);
                    res.add(new ArrayList<>(path));
                }
            }
        }
        return res;
    }

    public void dfs(boolean[][] visited,int[][] heights,int x,int y,int preH){
        if (x<0||y<0||x>=heights.length||y>=heights[0].length||visited[x][y]||heights[x][y]<preH){
            return;
        }
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nextX = x+dir[i][0];
            int nextY = y+dir[i][1];
            dfs(visited,heights,nextX,nextY,heights[x][y]);
        }


    }
}
